TNotes.leetcode

Appearance

0056. 合并区间【中等】

0056. 合并区间【中等】 ​

1. 📝 题目描述 ​

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [start_i, end_i]。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

示例 1：

输入：intervals = [
  [1, 3],
  [2, 6],
  [8, 10],
  [15, 18]
]

输出：[
  [1, 6],
  [8, 10],
  [15, 18]
]

解释：区间 [1, 3] 和 [2, 6] 重叠, 将它们合并为 [1, 6]。

示例 2：

输入：intervals = [
  [1, 4],
  [4, 5]
]

输出：[
  [1, 5]
]

解释：区间 [1, 4] 和 [4, 5] 可被视为重叠区间。

提示：

  • 1 <= intervals.length <= 10^4
  • intervals[i].length == 2
  • 0 <= starti <= endi <= 10^4

2. 🎯 s.1 - 排序 + 贪心合并 ​

c
/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int compareIntervals(const void* a, const void* b) {
	int* intervalA = *(int**)a;
	int* intervalB = *(int**)b;
	if (intervalA[0] != intervalB[0]) {
		return intervalA[0] - intervalB[0];
	}
	return intervalA[1] - intervalB[1];
}

int** merge(int** intervals, int intervalsSize, int* intervalsColSize,
			int* returnSize, int** returnColumnSizes) {
	qsort(intervals, intervalsSize, sizeof(int*), compareIntervals);

	int** result = (int**)malloc(sizeof(int*) * intervalsSize);
	*returnColumnSizes = (int*)malloc(sizeof(int) * intervalsSize);

	int currentStart = intervals[0][0];
	int currentEnd = intervals[0][1];
	int count = 0;

	for (int i = 1; i < intervalsSize; i++) {
		if (intervals[i][0] <= currentEnd) {
			if (intervals[i][1] > currentEnd) {
				currentEnd = intervals[i][1];
			}
		} else {
			result[count] = (int*)malloc(sizeof(int) * 2);
			result[count][0] = currentStart;
			result[count][1] = currentEnd;
			(*returnColumnSizes)[count] = 2;
			count++;

			currentStart = intervals[i][0];
			currentEnd = intervals[i][1];
		}
	}

	result[count] = (int*)malloc(sizeof(int) * 2);
	result[count][0] = currentStart;
	result[count][1] = currentEnd;
	(*returnColumnSizes)[count] = 2;
	count++;

	*returnSize = count;
	return result;
}
js
/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function (intervals) {
	intervals.sort((a, b) => a[0] - b[0])

	const result = [intervals[0]]

	for (let i = 1; i < intervals.length; i++) {
		const last = result[result.length - 1]
		const current = intervals[i]

		if (current[0] <= last[1]) {
			last[1] = Math.max(last[1], current[1])
		} else {
			result.push(current)
		}
	}

	return result
}
py
class Solution:
	def merge(self, intervals: list[list[int]]) -> list[list[int]]:
		intervals.sort(key=lambda interval: interval[0])

		result = [intervals[0][:]]

		for start, end in intervals[1:]:
			if start <= result[-1][1]:
				result[-1][1] = max(result[-1][1], end)
			else:
				result.append([start, end])

		return result
  • 时间复杂度：O(nlog⁡n)，其中 n 是区间数组的长度，排序后只需再线性扫描一次
  • 空间复杂度：O(n)，主要取决于排序过程的辅助空间，若不计排序开销则合并过程只使用常数额外空间

算法思路：

  • 先按区间左端点从小到大排序，这样所有可能发生重叠的区间都会在遍历时相邻出现
  • 维护结果数组中的最后一个区间 last，表示当前已经合并出的最新区间
  • 遍历每个区间时，如果当前区间的左端点 start 不大于 last 的右端点 end，说明两个区间重叠，只需更新右端点为两者较大值
  • 如果当前区间和 last 不重叠，就把它作为一个新的独立区间加入结果数组
  • 遍历结束后，结果数组中剩下的就是所有合并完成后的不重叠区间

Discussions